package cn.leonis.leetcode;

/**
 * @Author Tobi
 * @Date 2021-07-14 上午12:31
 * 在二维矩阵中搜索
 */
public class Search2DMatrixSolution {

    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        // int[][] matrix = new int[][]{{1}};
        int target = 6;
        Search2DMatrixSolution solution = new Search2DMatrixSolution();
        System.out.println(solution.searchMatrix1(matrix, target));
    }

    /**
     * 首先在第一列找出相关的位置，然后遍历行
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowIndex = searchFirstColumn(matrix, target);
        if (rowIndex < 0) {
            return false;
        }
        return binarySearchRow(matrix[rowIndex], target);
    }

    /**
     * 搜索第一列，然后找出要搜寻的行
     * @param matrix
     * @param target
     * @return
     */
    public int searchFirstColumn(int[][] matrix, int target) {
        int low = -1, high = matrix.length - 1;
        while (low < high) {
            int mid = ((high - low + 1) >>> 1) + low;
            if (matrix[mid][0] <= target) {
                low = mid;
            }else {
                high = mid - 1;
            }
        }
        return low;
    }

    /**
     * 在行里查找
     * @param row
     * @param target
     * @return
     */
    public boolean binarySearchRow(int[] row, int target) {
        int left = 0, right = row.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (row[mid] < target) {
                left = mid + 1;
            }else if (row[mid] > target) {
                right = mid - 1;
            }else {
                return true;
            }
        }
        return false;
    }

    /**
     * 假设矩阵是整齐的，然后将其摊平来二分查找
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix1(int[][] matrix, int target) {
        int length = matrix.length;
        int left = 0, right = length * matrix[0].length;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (matrix[mid / length][mid % length] == target) {
                return true;
            }else if (matrix[mid / length][mid % length] > target) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return false;
    }
}
